|
In mathematics, a Kleene algebra ( ; named after Stephen Cole Kleene) is an idempotent (and thus partially ordered) semiring endowed with a closure operator. It generalizes the operations known from regular expressions. == Definition == Various inequivalent definitions of Kleene algebras and related structures have been given in the literature.〔For a survey, see: 〕 Here we will give the definition that seems to be the most common nowadays. A Kleene algebra is a set ''A'' together with two binary operations + : ''A'' × ''A'' → ''A'' and · : ''A'' × ''A'' → ''A'' and one function * : ''A'' → ''A'', written as ''a'' + ''b'', ''ab'' and ''a'' * respectively, so that the following axioms are satisfied. * Associativity of + and ·: ''a'' + (''b'' + ''c'') = (''a'' + ''b'') + ''c'' and ''a''(''bc'') = (''ab'')''c'' for all ''a'', ''b'', ''c'' in ''A''. * Commutativity of +: ''a'' + ''b'' = ''b'' + ''a'' for all ''a'', ''b'' in ''A'' * Distributivity: ''a''(''b'' + ''c'') = (''ab'') + (''ac'') and (''b'' + ''c'')''a'' = (''ba'') + (''ca'') for all ''a'', ''b'', ''c'' in ''A'' * Identity elements for + and ·: There exists an element 0 in ''A'' such that for all ''a'' in ''A'': ''a'' + 0 = 0 + ''a'' = ''a''. There exists an element 1 in ''A'' such that for all ''a'' in ''A'': ''a''1 = 1''a'' = ''a''. * ''a''0 = 0''a'' = 0 for all ''a'' in ''A''. The above axioms define a semiring. We further require: * + is idempotent: ''a'' + ''a'' = ''a'' for all ''a'' in ''A''. It is now possible to define a partial order ≤ on ''A'' by setting ''a'' ≤ ''b'' if and only if ''a'' + ''b'' = ''b'' (or equivalently: ''a'' ≤ ''b'' if and only if there exists an ''x'' in ''A'' such that ''a'' + ''x'' = ''b''; with any definition, ''a'' ≤ ''b'' ≤ ''a'' implies ''a'' = ''b''). With this order we can formulate the last two axioms about the operation *: * 1 + ''a''(''a'' *) ≤ ''a'' * for all ''a'' in ''A''. * 1 + (''a'' *)''a'' ≤ ''a'' * for all ''a'' in ''A''. * if ''a'' and ''x'' are in ''A'' such that ''ax'' ≤ ''x'', then ''a'' *''x'' ≤ ''x'' * if ''a'' and ''x'' are in ''A'' such that ''xa'' ≤ ''x'', then ''x''(''a'' *) ≤ ''x'' 〔Kozen (1990), sect.2.1, p.3〕 Intuitively, one should think of ''a'' + ''b'' as the "union" or the "least upper bound" of ''a'' and ''b'' and of ''ab'' as some multiplication which is monotonic, in the sense that ''a'' ≤ ''b'' implies ''ax'' ≤ ''bx''. The idea behind the star operator is ''a'' * = 1 + ''a'' + ''aa'' + ''aaa'' + ... From the standpoint of programming language theory, one may also interpret + as "choice", · as "sequencing" and * as "iteration". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kleene algebra」の詳細全文を読む スポンサード リンク
|